package simple;

import java.util.Objects;

/**
 * @author 杜伟毅
 * @version 1.0
 * @since 2025/10/08
 * <p>
 * 21. 合并两个有序链表
 * 简单
 * 相关标签
 * premium lock icon
 * 相关企业
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * <p>
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * <p>
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 */
public class LinkedListMerger {

    /*
    通俗解释：
    这段代码像两个人排队买票：
    基本情况：
        如果一个人没来（list1为空），另一个直接买票（返回list2）
        如果另一个人没来（list2为空），这个人直接买票（返回list1）
    比较过程：
        比较两人谁排得靠前（值更小）
        让排得靠前的人先买票（作为新节点）
        然后让这个人离开队伍（list1.next或list2.next），剩下的人继续比较
    递归合并：
        每次只处理当前最靠前的人
        剩下的人重复同样的比较过程
        直到所有人都买完票（链表合并完成）
    这种递归解法就像"每次选最小的人，剩下的交给别人处理"，最终得到有序合并的队列。
    
    
    */

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果list1为空，直接返回list2（包含剩余节点）
        if (Objects.isNull(list1)) return list2;
        // 如果list2为空，直接返回list1（包含剩余节点）
        if (Objects.isNull(list2)) return list1;

        // 创建新节点作为当前合并结果的起点
        ListNode temp = new ListNode();

        // 比较两个链表当前节点的值
        if (list1.val <= list2.val) {
            // 如果list1的值更小，使用list1的值作为新节点的值
            temp.val = list1.val;
            // 递归合并list1的下一个节点和list2
            temp.next = mergeTwoLists(list1.next, list2);
        } else {
            // 如果list2的值更小，使用list2的值作为新节点的值
            temp.val = list2.val;
            // 递归合并list1和list2的下一个节点
            temp.next = mergeTwoLists(list1, list2.next);
        }

        // 返回当前合并后的链表头节点
        return temp;
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode list2 = new ListNode(3, new ListNode(4, new ListNode(6)));

        LinkedListMerger merger = new LinkedListMerger();
        System.out.println(merger.mergeTwoLists(list1, list2));
    }
}
